import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/25 10:38
 * @description 大佬做法
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int[] arr = {3, 5, 1, 2 , 4};
        solution2.findLatestStep(arr, 1);
    }
    public int findLatestStep(int[] arr, int m) {

        // 段：1 1 1 1 1 1
        // 核心是1个指针定义段：如果是段头就指向段尾，如果是段尾就指向段头，段长度 = abs(link[i] - i) + 1

        // link数组：头尾各有一个空点，所以是大小是 n + 2：_ 1 2 3 4 5 _
        int[] link = new int[arr.length + 2];

        // 段长为 m 的个数
        int cnt = 0;
        int res = -1;

        for (int i = 0; i < arr.length; i++) {

            int x = arr[i];
            // 左段 link
            int l = link[x - 1] != 0 ? link[x - 1] : x;
            // 右段 link
            int r = link[x + 1] != 0 ? link[x + 1] : x;

            // 修改 cnt
            if (x - l == m) {
                cnt--;
            }
            if (r - x == m) {
                cnt--;
            }
            if (r - l + 1 == m) {
                cnt++;
            }
            if (cnt > 0) {
                res = i + 1;
            }

            // 合并段，这里是精髓，向左边提供 合并区间的最大值， 向右边提供合并区间的 最小值
            link[l] = r;
            link[r] = l;
        }
        return res;
    }
}
